  class MySingleLinkedList{
    static class  ListNode{
        public int val;
        public ListNode next;
        public  ListNode(int val){
            this.val=val;
        }
    }
    public  ListNode head;
//    public void createList(){
//        ListNode node1=new ListNode(12);
//        ListNode node2=new ListNode(23);
//        ListNode node3=new ListNode(34);
//        ListNode node4=new ListNode(45);
//        ListNode node5=new ListNode(56);
//
//        node1.next=node2;
//        node2.next=node3;
//        node3.next=node4;
//        node4.next=node5;
//        this.head=node1;
//    }
    public  void display(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
      public  void display(ListNode newHead){
          ListNode cur=newHead;
          while(cur!=null){
              System.out.print(cur.val+" ");
              cur=cur.next;
          }
          System.out.println();
      }
    public int side(){
        int count=0;
        ListNode cur=head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public void addFirst(int val){
        ListNode node=new ListNode(val);
        node.next=this.head;
        head=node;
    }//头插法
      public void addLast(int val){

        ListNode node=new ListNode(val);
        if (head==null){
              head=node;
              return;
          }
          ListNode cur=head;
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
      }
      public void addIndex(int index,int val){
        //判断下标的合法性
          try {
              checkIndex(index);
          }catch (Exception e){
              e.printStackTrace();
          }
          if (index==0){
              addFirst(val);
              return;
          }
          if (index==side()){
              addLast(val);
              return;
          }

         ListNode cur=findIndexSubOne(index);
          ListNode listNode=new ListNode(val);
          listNode.next=cur.next;
          cur.next=listNode;
      }
      private ListNode findIndexSubOne(int index){
          ListNode cur=head;
         int count=0;
         while (count!=index-1){
             cur=cur.next;
             count++;
         }
         return cur;
      }
      private void checkIndex(int index)throws IndexNotLegalException{
        if (index<0||index>side()){
            throw new IndexNotLegalException("下标不合法");
        }
      }
      public boolean contains(int val){
        ListNode cur=head;
        while (cur!=null){
            if (cur.val==val){
                return true;
            }
            cur=cur.next;
        }
        return false;
      }
      public void remove1(int val){
          if(head==null){
              return;
          }
        if (contains(val)==false){
            return;
        }
        ListNode cur=head;
        if (cur.val==val){
            head=cur.next;
            return;
        }
        while (cur.next.val!=val){
            cur=cur.next;
        }
        cur.next=cur.next.next;
      }
      public void remove(int val){
        if(head==null){
            return;
        }
        if(head.val==val){
            head=head.next;
        }
        ListNode cur=head;
        while (cur.next!=null){
            if(cur.next.val==val){
                cur.next=cur.next.next;
                return;
            }
            cur=cur.next;
        }
      }
      public void removeAllKey(int val) {
          if (head == null) {
              return;
          }
          ListNode prev=head;
          ListNode cur=head.next;
          while (cur!=null){
              if(cur.val==val){
                  prev.next=cur.next;
              }else {
                  prev=cur;
              }
              cur=cur.next;

          }
          if (head.val==val){
              head=head.next;
          }

      }
      public void clear(){
        //法一
        //head=null;
        //法二
          ListNode cur=head;
          ListNode curNext=head.next;
          while (curNext.next!=null){
              cur.next=null;
              cur=curNext;
              curNext=curNext.next;
          }
          head=null;

      }
      //翻转列表
      public void reverseList(){
        if (head==null){
            return;
        }
        ListNode cur=head.next;
        ListNode curNext=cur.next;
        head.next=null;
        while (cur!=null) {
            cur.next = head;
            head = cur;
            cur = curNext;
            if(curNext!=null) {
                curNext = curNext.next;
            }
        }

      }
      //返回中间值（快慢指针）
      public ListNode returnMid(){
        ListNode slow=head;
        ListNode fast=head;
//        if (side()%2==0){
//            while (fast!=null){
//                slow=slow.next;
//                fast=fast.next.next;
//            }
//            return slow;
//        }
//        else {
//            while (fast.next!=null){
//                slow=slow.next;
//                fast=fast.next.next;
//            }
//            return slow;
//        }
          while (fast!=null&&fast.next!=null){//两者不能调换位置
              slow=slow.next;
              fast=fast.next.next;
          }
          return slow;
      }
      public  int kthToLast(int k){
        if (k<0||head==null){
            return -1;
        }
          ListNode slow=head;
          ListNode fast=head;
          int count=0;
          while (count!=k-1){
              fast=fast.next;
              if (fast==null){
                  return -1;
              }
              count++;
          }
          while (fast.next!=null){
              slow=slow.next;
              fast=fast.next;
          }
          return slow.val;

      }
      //两个升序的列表，合并成一个升序的列表
      public ListNode mergeTowLists(ListNode head1,ListNode head2){
        ListNode listNode=new ListNode(-1);
        ListNode newHead=listNode;
        ListNode tmp=newHead;
        while (head1!=null&&head2!=null){
            if (head1.val<head2.val){
                tmp.next=head1;
                head1=head1.next;
                tmp=tmp.next;
            }
            else {
                tmp.next=head2;
                head2=head2.next;
                tmp=tmp.next;
            }
            }
        if (head1==null){
              tmp.next=head2;
        }if (head2==null){
              tmp.next=head1;
          }
          return newHead.next;
      }
      //给一个数值x，使列表中小于x放x之前，大于x的放x之后
      public ListNode partition(int k){
        if (head==null){
            return null;
        }
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=head;

        while (cur!=null){
            if(cur.val<k){
                if(bs==null){
                    bs=be=cur;
                }else {
                    be.next=cur;
                    be=be.next;
                }
                cur=cur.next;
            }else {
                if(as==null){
                    as=ae=cur;

                }else {
                    ae.next=cur;
                    ae=ae.next;
                }
                cur=cur.next;
            }
        }
        if(bs==null){
            return as;
        }
        be.next=as;
        if(as!=null){
            ae.next=null;
        }
        return bs;
      }//考虑两个部分是否为空
//回文
      //1找中间节点2，翻转后半部分
public boolean chkPalindrome(){
        if (head==null){
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;

        while (cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        while (head!=slow){
            if (head.val!=slow.val){
                return false;
            }
            if (head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;
        }
        return false;
}
//成环的判断，即成环的节点
      public ListNode detectCycle(){
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (slow==fast){
                break;
            }
        }
        if (fast==null||fast.next==null){
            return null;
        }

        fast=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;

      }
public void createLoop(){
        ListNode cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=head.next;
    }

}
public class Text {
    public static void main(String[] args) {
        MySingleLinkedList msl1=new MySingleLinkedList();
        msl1.addLast(1);
        msl1.addLast(3);
        msl1.addLast(5);
        msl1.addLast(7);
        msl1.addLast(9);
        msl1.createLoop();
        MySingleLinkedList.ListNode ret=msl1.detectCycle();
        System.out.println(ret.val);

    }

    //找到两个数列相交的节点
    public static MySingleLinkedList.ListNode getIntersectionNode(MySingleLinkedList.ListNode head1, MySingleLinkedList.ListNode head2){
    MySingleLinkedList.ListNode p1=head1;//p1==long
    MySingleLinkedList.ListNode p2=head2;//p2==short
    int len1=0;
    int len2=0;
    while (p1!=null){
        p1=p1.next;
        len1++;
    }
    while (p2!=null){
        p2=p2.next;
        len2++;
    }
    int len=len1-len2;
    p1=head1;//p1==long
    p2=head2;//p2==short
    if (len<0){
        p1=head2;
        p2=head1;
        len=len2-len1;
    }
    while (len!=0){
        p1=p1.next;
        len--;
    }
    while (p1!=p2){
        p1=p1.next;
        p2=p2.next;
    }
    return p1;

}
//让两个列表进行相交
    public static void intersectList(MySingleLinkedList.ListNode head1, MySingleLinkedList.ListNode head2){
    head1.next.next=head2.next.next;
    }

    public static void main5(String[] args) {
        MySingleLinkedList msl1=new MySingleLinkedList();
        msl1.addLast(1);
        msl1.addLast(3);
        msl1.addLast(5);
        msl1.addLast(7);
        msl1.addLast(9);
        MySingleLinkedList msl2=new MySingleLinkedList();
        msl2.addLast(2);
        msl2.addLast(4);
        msl2.addLast(6);
        msl2.addLast(8);
        msl2.addLast(10);
        intersectList(msl1.head,msl2.head);
        msl1.display();
        msl2.display();

        MySingleLinkedList.ListNode ret=getIntersectionNode(msl1.head,msl2.head);
        System.out.println(ret.val);
    }
    public static void main4(String[] args) {
        MySingleLinkedList msl1=new MySingleLinkedList();
        msl1.addLast(1);
        msl1.addLast(200);
        msl1.addLast(5);
        msl1.addLast(200);
        msl1.addLast(1);
        System.out.println(msl1.chkPalindrome());
    }
    public static void main3(String[] args) {
        MySingleLinkedList msl1=new MySingleLinkedList();
        msl1.addLast(1);
        msl1.addLast(200);
        msl1.addLast(5);
        msl1.addLast(19);
        msl1.addLast(100);
        MySingleLinkedList.ListNode ret=msl1.partition(12);
        msl1.display(ret);
    }
    //两个升序的列表，合并成一个升序的列表
    public static MySingleLinkedList.ListNode mergeTowLists(MySingleLinkedList.ListNode head1, MySingleLinkedList.ListNode head2){
        MySingleLinkedList.ListNode listNode=new MySingleLinkedList.ListNode(-1);
        MySingleLinkedList.ListNode newHead=listNode;
        MySingleLinkedList.ListNode tmp=newHead;
        while (head1!=null&&head2!=null){
            if (head1.val<head2.val){
                tmp.next=head1;
                head1=head1.next;
                tmp=tmp.next;
            }
            else {
                tmp.next=head2;
                head2=head2.next;
                tmp=tmp.next;
            }
        }
        if (head1==null){
            tmp.next=head2;
        }if (head2==null){
            tmp.next=head1;
        }
        return newHead.next;
    }

    public static void main2(String[] args) {
        MySingleLinkedList msl1=new MySingleLinkedList();
        msl1.addLast(1);
        msl1.addLast(3);
        msl1.addLast(5);
        msl1.addLast(7);
        msl1.addLast(9);
        MySingleLinkedList msl2=new MySingleLinkedList();
        msl1.addLast(2);
        msl1.addLast(4);
        msl1.addLast(6);
        msl1.addLast(8);
        msl1.addLast(10);
        MySingleLinkedList.ListNode neaHead=mergeTowLists(msl1.head,msl2.head);
        msl1.display();

    }
    public static void main1(String[] args) {
        MySingleLinkedList msl=new MySingleLinkedList();
        //msl.createList();
        //msl.display();
        msl.addIndex(2,99);
        msl.addIndex(4,99);
        msl.addIndex(2,33);
        msl.display();
        //msl.removeAllKey(99);
        //msl.clear();
        //msl.reverseList();
        MySingleLinkedList.ListNode ret=msl.returnMid();
        System.out.println(ret.val);
        msl.display();
        //System.out.println(msl.side());
    }
}
